package com.srunpass.algorithm;

import java.util.HashMap;
import java.util.Map;

public class 青蛙过河 {

    public static void main(String[] args) {
        int [] s  ={0,1,3,5,6,8,12,17};
        青蛙过河 ss = new 青蛙过河();
        ss.canCross(s);
    }

    int[] stones;
    Map<Integer,Integer> map;
    Map<String,Boolean>  res = new HashMap<>();
    int len;

    public boolean canCross(int[] stones) {
        this.stones = stones;
        len = stones.length;
        map = new HashMap<>(stones.length);
        for (int i = 0; i < stones.length; i++) {
            map.put(stones[i], i);
        }
        return dfs(0,1);
    }

    public boolean dfs(Integer i,int lastStep) {
        String key = i+"-"+ lastStep;
        Boolean b = res.get(key);
        if(b!=null){
          return b;
        }
        if(i==null||lastStep==0||i>=len){
            res.put(key,false);
            return false;
        }
        if(i==len-1){
            return true;
        }
        boolean b1 =false;
        Integer nextIndex = map.get(stones[i] + lastStep);
//        if(lastStep>1){
            b1=dfs(nextIndex,lastStep-1 );
//        }
        b1 = b1||dfs(nextIndex, lastStep);
        b1 = b1||dfs(nextIndex, lastStep + 1);

        res.put(key,b1);
        return b1;
    }
}
